\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm,epsfig}
\usepackage[left=1in,top=1in,right=1in,bottom=1in,nohead]{geometry}
%\usepackage{fullpage}
\usepackage{subfigure}
\usepackage{times}
\usepackage{url}

\begin{document}

\input{macros}


\title{Update --14 June 2012}


\author{}
\date{}
 
\maketitle

\section{Power-law-like Trees} 

In their paper ~\cite{bolobasriorddegseq}, Bellabas and Riordan derive an approximation of the expected degree of a vertex inserted in the $s^{th}$ place in a preferential attachment graph process, for edge constant $m=1$. This formula is:
\begin{equation}
E(d_{G^n_1}(v_s)) = \sqrt{n / s} (1 + O(1/s))
\end{equation}
We will build a tree that obeys this formula for the expected degree of a vertex at insertion step $s$, and then show that a cobra-walk will cover this tree in $O(\sqrt{n} \log^2 n )$ time. 
\begin{definition}  Power Law Tree \\
Define a Power Law Tree of size n  - PLT(n) - construction as follows. Start with root $r$. Using equation 1, we find that the root has $\sqrt{n}$ children. We then insert these one by one. Now we want to compute the degree of the leftmost child, which is inserted in place $2$, meaning it has $n^{1/2}$ children as well. Assuming the tree is symmetric and every node at this level has the same number of children, there are $n^{1/2} n^{1/2}$ children at the third level. The leftmost child is inserted in the $n^{1/2} + 2$-th place, thus giving it $(n / (n^{1/2})^{1/2} = n^{1/4}$ children. The next level will have 
\end{definition}


\end{document}
